//实现标准库头文件<numeric>中accumulate函数的并行版本
#include <iostream>
#include <thread>
#include <numeric>
#include <algorithm>
#include <vector>
#include <functional>
#include <utility>
#include <chrono>
#include <math.h>

using std::thread;
using std::vector;
using std::accumulate;
using std::cout;
using std::endl;

// 被执行的函数
template <typename Iterator> class Accum
{
  public:
    void operator()(Iterator first, Iterator last, Iterator dst)
    {
        std::copy(first, last, dst);
    }
};

// 分发任务的函数
template <typename Iterator> void ParallelAccum(Iterator first, Iterator last, Iterator dst)
{
    //计算迭代器中包含的元素数量
    const unsigned int len = std::distance(first, last);
    //若迭代器中没有元素则直接返回
    if (!len)
    {
        return;
    }

    //获取机器支持的并发线程数
    const unsigned int num_thread = thread::hardware_concurrency();

    //最终实际上每个线程处理的元素个数
    const unsigned int block_size = len / num_thread;
    //启动比num_thread - 1个线程，因为main函数本身已开启一个线程
    vector<thread> threads(num_thread - 1);

    //开始并行计算
    Iterator block_begin = first;
    for (unsigned int i = 0; i < (num_thread - 1); ++i)
    {
        Iterator block_end = block_begin;
        //将迭代器向前推进一个块,到达当前块的末尾位置
        std::advance(block_end, block_size);
        //传递参数,通常情况下thread的构造函数将复制所提供的参数,需要将模板参数转为引用
        threads[i]  = thread(Accum<Iterator>(), block_begin, block_end, dst + block_size * i);
        block_begin = block_end;
    }
    //处理最后一个线程,由于block_size = len / num_thread得到的结果不一定为整数,该线程处理剩余的所有元素
    Accum<Iterator>()(block_begin, last, dst+ (num_thread - 1)*block_size);
    //对threads中所有线程调用join()
    std::for_each(threads.begin(), threads.end(), std::mem_fn(&thread::join));
    //
    return;
}

// 计时结构
uint64_t t1, t2, tc;

void time_begin()
{
    t1 = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
}

float time_end()
{
    t2 = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
    return (t2 - t1);
}

int main()
{
    // 装备任务队列
    vector<int8_t> i_vec;
    vector<int8_t> to_vec;
    for (int i = 1; i != 10000 * 10000; ++i) { i_vec.push_back(i % 255); }
    to_vec.reserve(i_vec.size());
    // 并行计算示例
    time_begin();
    ParallelAccum(i_vec.begin(), i_vec.end(), to_vec.begin());
    cout << "time: " << time_end() << endl;

    // 一般计算示例
    time_begin();
    Accum<vector<int8_t>::iterator> a;
    a(i_vec.begin(), i_vec.end(), to_vec.begin());
    cout << "time: " << time_end() << endl;

    return 0;
}
